package bstsetcode;

import java.util.Arrays;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/16 7:04
 * 时间复杂度：
 * 使用插入排序优化
 */
public class MergeSort3 {

    public static <E extends Comparable<E>>  void sorted(E[] data){
        int left = 0;
        int right = data.length-1;
        mergeSorted(data,left,right);
    }

    private static <E extends Comparable<E>> void mergeSorted(E[] data, int left, int right) {
//        if(left >= right) {
//            return;
//        }

        if(right - left <= 15){
            InsertionSort.sort(data,left,right);
            return;
        }

        int mid = (left + right )/2;

        //对arr[l,mid]进行排序
        mergeSorted(data,left,mid);
        mergeSorted(data,mid+1,right);
        //合并
        merge(data,left,mid,right);

    }

    private static <E extends Comparable<E>> void merge(E[] data, int left, int mid, int right) {
            E[] temp = Arrays.copyOfRange(data,left,right+1);

            int i = left,j=mid+1;

        for (int k = left; k <= right; k++) {
            //判断越界的情况
            if(i > mid){ //左边数组没有数据，直接赋值有边数组的值
                data[k] = temp[j-left];
                j++;
            }else if( j > right){
                data[k] = temp[i-left];
                i++;
            }else if(temp[i-left].compareTo(temp[j-left]) <= 0){
                data[k]=temp[i-left];
                i++;
            }else{
                data[k]=temp[j-left];
                j++;
            }
        }

    }

    public static void main(String[] args) {


//        int n = 100000;
//        Integer[] arr1 =ArrayGenerator.generateRandomArray(n,n);
//        SortHelper.sortTest("MergeSort3",arr1);

        int[] dataSize = {100000,1000000,10000000};
        for(int n : dataSize){
            Integer[] arr1 =ArrayGenerator.generateRandomArray(n,n);
            Integer[] copy=Arrays.copyOf(arr1,arr1.length);

            SortHelper.sortTest("MergeSort",arr1);
            SortHelper.sortTest("MergeSort3",copy);
            System.out.println("---------------");
        }

        /**
         * 细微的提升：
         * MergeSort , n = 100000: 0.049672 s
         * MergeSort3 , n = 100000: 0.064110 s
         * ---------------
         * MergeSort , n = 1000000: 0.355218 s
         * MergeSort3 , n = 1000000: 0.271871 s
         * ---------------
         * MergeSort , n = 10000000: 3.278994 s
         * MergeSort3 , n = 10000000: 3.060556 s
         * ---------------
         */


    }

}
